package org.example.sword2offer.primary;

import java.util.ArrayList;

/**
 * @author: lynn
 * @Descript: 和为S的连续正数序列
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 * @date: 2021/3/21 17:56
 * @version: 1.0
 */
public class Q41_FindContinuousSequence {

    public static void main(String[] args) {
        System.out.println(FindContinuousSequence(3));
    }

    //滑动窗解法
    private static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if (sum<=2){
            return res;
        }
        int plow=1,phigt=2;
        while (phigt>plow){
            int curSum=((plow+phigt)*(phigt-plow+1)/2);
            if (curSum<sum){
                phigt++;
            }else if (curSum>sum){
                plow++;
            }else {
                ArrayList<Integer> arrayList=new ArrayList<>();
                for (int k = plow; k <=phigt ; k++) {
                    //add时要用k-plow
                    arrayList.add(k-plow,k);
                }
                res.add(arrayList);
                plow++;
            }
        }
        return res;
    }
}
